#include <iostream>
#include <queue>

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int num) : val(num), left(nullptr), right(nullptr) {}
};

int GetMaxDepth(TreeNode *root)
{
    if (!root) return 0;
    std::queue<TreeNode*> q;
    q.push(root);
    int depth = 0;
    while (!q.empty())
    {
        ++depth;
        size_t level = q.size();

        while (level--)
        {
            auto cur_node = q.front();
            q.pop();
            if (!cur_node->left) q.push(cur_node->left);
            if (!cur_node->right) q.push(cur_node->right);
        }
    }
    
    return depth;
}

int main(int argc, char **argv)
{
    TreeNode* root = new TreeNode();
    int depth = GetMaxDepth(root);
    std::cout << "depth: " << depth << std::endl;
    return 0;
}